package com.jjlin.chapter_1;

import java.util.*;
public class CD15 {

    public static int[] getMaxWindow(int[] nums, int w){
        if(nums == null || w < 1 || w > nums.length)
            return new int[0];
        //使用一个双端队列来保存下标
        //保持双端队列中的下标所对应的数从队首到队尾是降序的
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - w + 1];
        int index = 0;
        for(int i = 0; i < nums.length; i++){
            //去掉窗口中小于等于nums[i]的的数下标（注意等于也去掉）
            while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i])
                deque.pollLast();
            deque.addLast(i);//加入下标
            if(deque.peekFirst() == i - w)//如果队首下标不在窗口中则删除
                deque.removeFirst();
            if(i >= w - 1)//形成窗口时res记录窗口最大值
                res[index++] = nums[deque.peekFirst()];
        }
        return res;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++)
            nums[i] = sc.nextInt();
        int[] res = getMaxWindow(nums, w);
        for(int i = 0; i < res.length; i++)
            System.out.print(res[i] + " ");
    }
}
